{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# ALGORITHMS AND DATA STRUCTURES\n",
    "\n",
    "The goal of this chapter is to help you develop some general intuitions about\n",
    "\n",
    "* <b>how to approach questions of efficiency</b>.\n",
    "\n",
    "The major point was that the key to efficiency is\n",
    "\n",
    "* a <b>good algorithm</b>,\n",
    "\n",
    "* not <b>clever coding tricks</b>.\n",
    "\n",
    "What we do instead is learn to <b>reduce</b> the most complex aspects of the problems with which we are faced <b>to previously solved problems</b>. \n",
    "\n",
    "More specifically, we:\n",
    "\n",
    "* Develop an <b>understanding of the inherent complexity</b> of the problem with which we are faced,\n",
    "\n",
    "* Think about how to **break** that problem up <b>into subproblems</b> \n",
    "\n",
    "* Relate those subproblems to other problems for which <b>efficient algorithms already exist</b>\n",
    "\n",
    "**Keep in mind ：**\n",
    "\n",
    "* The **most efficient** algorithm is **not always** the algorithm of **choice.**\n",
    "\n",
    "* A program that does everything in the most efficient possible way is often\n",
    "\n",
    "   * <b>needlessly difficult to understand</b>.\n",
    "\n",
    "It is often **a good strategy** to :\n",
    "   \n",
    "* **start** by solving the problem at hand in the most **straightforward manner possible**\n",
    "\n",
    "* instrument it to **find** any computational **bottlenecks**\n",
    "\n",
    "* look for ways to <b>improve</b> the computational complexity of those parts of the program contributing to the bottlenecks.\n",
    " \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#  Search Algorithms\n",
    "\n",
    "A search algorithm is a method for finding an item or group of items with specific properties within a collection of items. \n",
    "\n",
    "We refer to the collection of items as a <b>search space</b>. \n",
    "\n",
    "The search space might be something concrete, such as a set of electronic medical records, or something abstract, such as the set of all integers.\n",
    "\n",
    "In this section, we will examine two algorithms for searching a list. \n",
    "\n",
    "Each meets **the specification:**\n",
    "\n",
    "```python\n",
    "def search(L, e):\n",
    "\"\"\"Assumes L is a list.\n",
    "   Returns True if e is in L and False otherwise\"\"\"\n",
    "```\n",
    "\n",
    "It is  semantically equivalent to the Python expression\n",
    "```python\n",
    "e in L\n",
    "``` \n",
    "\n",
    "## 1 Linear Search \n",
    "\n",
    "Python uses the following algorithm to determine if an element is in a list\n",
    "```python\n",
    "def search(L, e):\n",
    "    for i in range(len(L)): # O(len(L))\n",
    "        if L[i] == e:\n",
    "            return True\n",
    "    return False\n",
    "```\n",
    "\n",
    "If the element **e** is not in the list the algorithm will perform $O(len(L))$ tests\n",
    "\n",
    "* the complexity is <b>at linear</b> in the length of L.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting ./demo/src/LinearSearch.c\n"
     ]
    }
   ],
   "source": [
    "%%file ./demo/src/LinearSearch.c\n",
    "/* \n",
    "\n",
    " Search an array for the given key using Linear Search (LinearSearch.c)\n",
    "\n",
    "*/\n",
    "#include <stdio.h>\n",
    "#include <stdlib.h> \n",
    "\n",
    "int linearSearch(const int a[], int size, int key);\n",
    "\n",
    "// Search the array for the given key\n",
    "//   1 If found, return array index [0, size-1];\n",
    "//   2 otherwise, return size: 99's index is: 8 \n",
    "int linearSearch(const int a[], int size, int key) {\n",
    "   for (int i = 0; i < size; ++i) {\n",
    "      if (a[i] == key) return i;\n",
    "   }\n",
    "   return size;\n",
    "}\n",
    " \n",
    "\n",
    "int main() {\n",
    "   const int SIZE = 8;\n",
    "   int a1[8] = {8, 4, 5, 3, 2, 9, 4, 1};\n",
    " \n",
    "   int keys[3]={8,4,99};\n",
    "   for(int i=0; i<3; i++) \n",
    "       printf(\"%d's index is: %d \\n\",keys[i],linearSearch(a1,SIZE, keys[i]));\n",
    "   \n",
    "   return 0; \n",
    " }\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "!gcc -o ./demo/bin/LinearSearch.exe ./demo/src/LinearSearch.c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8's index is: 0 \n",
      "4's index is: 1 \n",
      "99's index is: 8 \n"
     ]
    }
   ],
   "source": [
    "!.\\demo\\bin\\LinearSearch.exe "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 2 Binary Search(有序表对分查找） \n",
    "\n",
    "Getting back to the problem of implementing \n",
    "\n",
    "* **search(L, e)**, is **O(len(L))**。\n",
    "\n",
    "The best we can do? Yes!\n",
    "\n",
    "* If we know <b>nothing about the relationship of the values</b> of the elements in the list and the order in which they are stored.\n",
    "\n",
    "In the **worst case**, we have to look at **each** element in L to determine whether L contains e\n",
    "\n",
    "what is the **best** case?\n",
    "\n",
    "But suppose we **know** something about the **order** in which elements are stored, \n",
    "\n",
    "* we have a list of integers stored in <b>ascending order</b>.\n",
    "\n",
    "We could change the implementation so that the search stops when it reaches a number larger than the number for which it is searching:\n",
    "\n",
    "```python\n",
    "def search(L, e):\n",
    "    \"\"\"Assumes L is a list, the elements of which are in\n",
    "       ascending order.\n",
    "       Returns True if e is in L and False otherwise\"\"\"\n",
    "    for i in range(len(L)):\n",
    "        if L[i] == e:\n",
    "            return True\n",
    "        if L[i] > e:  # ascending order\n",
    "            return False\n",
    "    return False\n",
    "```\n",
    "\n",
    "This would improve the **average** running time. \n",
    "\n",
    "\n",
    "### 2.1 <font color=\"blue\">Binary search</font>\n",
    "\n",
    "We can get a considerable **improvement** in the <font color=\"blue\">Worst-Case Complexity</font> by using an algorithm, \n",
    "\n",
    "* <b>binary search</b>,\n",
    "\n",
    "Here we rely on the **assumption** that the list is <font color=\"blue\">Ordered</font>.\n",
    "\n",
    "The idea is simple:\n",
    "\n",
    "* Pick an index, $i$, that divides the list `L` <b>roughly in half</b>.\n",
    "\n",
    "* Ask `if L[i] == e`.\n",
    "\n",
    "  * If not, ask whether $L[i]$ is larger or smaller than $e$.\n",
    "\n",
    "* Depending upon the answer, search either <b>the left or right half</b> of $L$ for $e$.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The follow specification says that the implementation may assume that **L** is <b>sorted in ascending order</b>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_search(L, e, low, high):\n",
    "    if low>high:\n",
    "        return -1\n",
    "    if high == low:\n",
    "        if L[low] == e:\n",
    "            return low\n",
    "        else:\n",
    "            return -1\n",
    "    mid = (low + high)//2  #  roughly in half of list. \n",
    "    if L[mid] == e:\n",
    "        return mid\n",
    "    if L[mid] > e:\n",
    "        if low == mid: #nothing left to search\n",
    "            return -1\n",
    "        else:\n",
    "            return binary_search(L, e, low, mid - 1)# left\n",
    "    else:\n",
    "        return bSearch(L, e, mid + 1, high)  # right\n",
    "        \n",
    "    \n",
    "def search(L, e):\n",
    "    \"\"\"Assumes L is a list, the elements of which are in\n",
    "          ascending order.\n",
    "       Returns the index of location if e is in L and -1 otherwise\"\"\"\n",
    "    if len(L) == 0:\n",
    "        return -1\n",
    "    else:\n",
    "        return binary_search(L, e, 0, len(L) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "4\n",
      "6\n",
      "-1\n"
     ]
    }
   ],
   "source": [
    "sortedlist = [1, 4, 5, 8, 12, 19, 24, 31, 43, 55]\n",
    "keys=[8,12,24,21]\n",
    "for key in keys:\n",
    "    print(search(sortedlist, key))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 The complexity of bSearch \n",
    "\n",
    "The complexity of **bSearch** depends only upon \n",
    "\n",
    "* <b>the number of <font color='blue'>recursive</font> calls</b>.\n",
    "\n",
    "The question is \n",
    "\n",
    "* **how many times** can the value of **high–low** be cut in half before **high–low == 0?**\n",
    "\n",
    "$2^?=high-low$\n",
    "\n",
    "then:\n",
    "\n",
    "$?=\\log_2 ^{(high-low)}$\n",
    "\n",
    "so, <b>high–low</b> can be cut in half at most <b>$\\log_2^{(high–low)}$</b> times before it reaches 0.\n",
    "\n",
    "The complexity of search is <b>O(log(len(L)))</b>."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3 Binary Search in C\n",
    "\n",
    "* bSearch.h\n",
    "* bSearch.c\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Writing ./demo/include/bSearch.h\n"
     ]
    }
   ],
   "source": [
    "%%file ./demo/include/bSearch.h\n",
    "\n",
    "/* Search an array for a key using Binary Search */\n",
    "\n",
    "#ifndef BSEARCH_H\n",
    "#define BSEARCH_H\n",
    "\n",
    "\n",
    "int bSearch(const int a[], int size, int key);\n",
    "\n",
    "#endif"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting ./demo/src/bSearch.c\n"
     ]
    }
   ],
   "source": [
    "%%file ./demo/src/bSearch.c\n",
    "/* \n",
    "\n",
    "Search an array for a key using Binary Search (bSearch.c)\n",
    "\n",
    "*/\n",
    "\n",
    "#include \"bSearch.h\"\n",
    "#include <stdio.h>\n",
    " \n",
    "int binarySearch(const int a[], int iLeft, int iRight, int key);\n",
    "void print(const int a[], int iLeft, int iRight);\n",
    "  \n",
    "// Search the array for the given key\n",
    "// If found, return array index; otherwise, return -1\n",
    "int bSearch(const int a[], int size, int key) {\n",
    "   // Call recursive helper function\n",
    "   return binarySearch(a, 0, size-1, key);\n",
    "}\n",
    " \n",
    "// Recursive helper function for binarySearch\n",
    "int binarySearch(const int a[], int iLeft, int iRight, int key) {\n",
    "  \n",
    "   // For tracing the algorithm\n",
    "   print(a, iLeft, iRight);\n",
    " \n",
    "   // Test for empty list\n",
    "   if (iLeft > iRight) return -1;\n",
    " \n",
    "   // Compare with middle element\n",
    "   int mid = (iRight + iLeft) / 2;  // truncate\n",
    "   if (key == a[mid]) {\n",
    "      return mid;\n",
    "   } else if (key < a[mid]) {\n",
    "      // Recursively search the lower half\n",
    "      binarySearch(a, iLeft, mid - 1, key);\n",
    "   } else {\n",
    "      // Recursively search the upper half\n",
    "      binarySearch(a, mid + 1, iRight, key);\n",
    "   }\n",
    "}\n",
    "\n",
    "// Print the contents of the given array from iLeft to iRight (inclusive)\n",
    "void print(const int a[], int iLeft, int iRight) {\n",
    "   printf(\"{\");\n",
    "   for (int i = iLeft; i <= iRight; ++i) {\n",
    "      printf(\"%d\",a[i]);\n",
    "      if (i < iRight) printf(\",\");\n",
    "   }\n",
    "   printf(\"} \\n\");\n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting ./demo/src/DemobSearch.c\n"
     ]
    }
   ],
   "source": [
    "%%file ./demo/src/DemobSearch.c\n",
    "\n",
    "#include <stdio.h>\n",
    "#include <stdlib.h> \n",
    "#include \"bSearch.h\" \n",
    "\n",
    "int main() {\n",
    "   const int SIZE = 10;\n",
    "   int a1[10] = {1, 4, 5, 8, 12, 19, 24, 31, 43, 55}; // sorted\n",
    " \n",
    "   int keys[4]={8,12,24,21};\n",
    "   for(int i=0; i<4; i++) \n",
    "       printf(\"%d's index is: %d \\n\",keys[i],bSearch(a1,  SIZE, keys[i]));\n",
    "   \n",
    "   return 0; \n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "!gcc -c -o ./demo/obj/bSearch.o ./demo/src/bSearch.c -I./demo/include\n",
    "!gcc -c -o ./demo/obj/DemobSearch.o ./demo/src/DemobSearch.c  -I./demo/include\n",
    "!gcc -o ./demo/bin/DemobSearch.exe ./demo/obj/DemobSearch.o ./demo/obj/bSearch.o"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1,4,5,8,12,19,24,31,43,55} \n",
      "{1,4,5,8} \n",
      "{5,8} \n",
      "{8} \n",
      "8's index is: 3 \n",
      "{1,4,5,8,12,19,24,31,43,55} \n",
      "12's index is: 4 \n",
      "{1,4,5,8,12,19,24,31,43,55} \n",
      "{19,24,31,43,55} \n",
      "{19,24} \n",
      "{24} \n",
      "24's index is: 6 \n",
      "{1,4,5,8,12,19,24,31,43,55} \n",
      "{19,24,31,43,55} \n",
      "{19,24} \n",
      "{24} \n",
      "{} \n",
      "21's index is: -1 \n"
     ]
    }
   ],
   "source": [
    "!.\\demo\\bin\\DemobSearch.exe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Further Reading\n",
    "\n",
    "* 严蔚敏，李冬梅，吴伟民. 数据结构（C语言版），人民邮电出版社（第2版）,2015年2月  \n",
    "\n",
    "\n",
    "* Mark Allen Weiss. Data Structures and Algorithm Analysis in C\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.7"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "197.475px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  },
  "widgets": {
   "state": {},
   "version": "1.1.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
